1174C - Ehab and a Special Coloring Problem - CodeForces Solution

 #include <iostream>
#include <string>
#include<stack>
#include<unordered_set>
#include<queue>
#include<deque>
#include<algorithm>
#include <cmath>
#include<ctime>
#include<map>
#include<set>
#include<vector>
#include<iomanip> // setprecision(number)   cout << fixed << setprecision(6);
#include<ctype.h> //  towlower toupper
#define sa(a,n) sort(a,a+n)
#define endl   "\n"
#define ll long long
#define tt int
#define str string
#define fs(n)              fixed<<setprecision(n)
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define leadzero(a) __builtin_clz(a)        // count leading zeroes
#define trailzero(a) __builtin_ctz(a)       // count trailing zeroes
#define bitcount(a) __builtin_popcount(a)   // count set bits
using namespace std;
ll prime[10000005];
void  sieve() {
    for (ll x = 2; x < 1e7; x++)
    {
        if(x!=2&&x%2!=0)
            prime[x] = 1;
    }
    for (ll x = 3; x * x < 1e7; x += 2) 
    {
        if (prime[x]) 
        {
            for (int j = x * x; j < 1e7; j += x + x)
                prime[j] = 0;
        }
    }
}
bool isPrime(ll n)
{
    if (n <= 1)
        return false;
    if (n <= 3)
        return true;
    if (n % 2 == 0 || n % 3 == 0)
        return false;
    for (ll i = 5; i * i <= n; i = i + 6)
        if (n % i == 0 || n % (i + 2) == 0)
            return false;
 
    return true;
}
ll lcm(ll x,ll y)
{
    return x * y / __gcd(x, y);
}
bool cm  (pair< int,string>p1  ,pair< int,string>p2)
 {
     if(p1.first==p2.first)
     return p1.second<p2.second;

      return p1.first>p2.first;
     
 }
 
 
// auto  it  = maxx.end(); it--; k=*it erase(it) ,, set<ll,greater<>>s;
//getline(cin, s1)
//auto it=upper_bound(v.begin(),v.end(),m);
int main() {
    fast;
    sieve();
    ll n,con=1;
    cin>>n;
    vector<ll>v(n+1,0);
    for(ll x=2;x<=n;x++)
    {
        if(v[x]==0)
        {
          for(ll i=x;i<=n;i+=x)
           v[i]=con;
           con++;
        }
       
    }
    for(ll x=2;x<=n;x++)
    cout << v[x] << " ";
}